package com.lfc.math;

public class Test {
    public static void main(String[] args) {
//        int[] nums = {9, 8, 4, 2, 1};
//        int low = 5, high = 14;
//        System.out.println(countPairs(nums, low, high));
//        System.out.println(countEvent(30));
//        System.out.println(reinitializePermutation(6));
        int[] val={3,4,5,8};
        int[] wegith={2,3,4,5};
        int W=8;
    }

//    public static int reinitializePermutation(int n) {
//        if (n == 2) return 1;
//        int k = 1, p = 2;
//        while (p != 1) {
//            k++;
//            p = 2 * p % (n - 1);
//        }
//        return k;
//    }


    public static int countEvent(int num) {
        int res = 0, i = 1;
        while (i <= num) {
            int a = i, sum = 0;
            while (a > 0) {
                sum += a % 10;
                a /= 10;
            }
            if (sum % 2 == 0) res++;
            i++;
        }
        return res;
    }

    public static int countPairs(int[] nums, int low, int high) {
        TrieNode node = new TrieNode();
        int ans = 0;
        for (int num : nums) {
            ans += getSlowerCount(node, high + 1, num) - getSlowerCount(node, low, num);
            insert(node, num);
        }
        return ans;
    }

    private static int getSlowerCount(TrieNode node, int compare, int cur) {
        int ans = 0;
        for (int i = 31; i >= 0; i--) {
            if (node == null) {
                return ans;
            }
            int comIndex = ((compare >>> i) & 1);
            int curIndex = ((cur >>> i) & 1);
            if (comIndex == 1) {
                if (node.children[curIndex] != null) {
                    ans += node.children[curIndex].count;
                }
                node = node.children[1 - curIndex];
            } else {
                node = node.children[curIndex];
            }
        }
        return ans;
    }

    private static void insert(TrieNode trieNode, int num) {
        TrieNode node = trieNode;
        for (int i = 31; i >= 0; i--) {
            int cur = ((num >>> i) & 1);
            if (node.children[cur] == null) {
                node.children[cur] = new TrieNode();
            }
            node = node.children[cur];
            node.count++;
        }
    }

    // 设置一个字典树
    static class TrieNode {
        // 设置字典树的值
        int count;
        TrieNode[] children = new TrieNode[2];
    }


}
